#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //题目中，原数组是单调递增的，所以可以使用二分法
        int l=0,r=nums.size();
        int mid = (l+r)/2;
        int ans = 0;
        while(l<r) {
            if(nums[mid] == target){
                ans+=cntNum(mid,nums,true);
                ans+=cntNum(mid,nums,false);
                ans+=1;
                return ans;
            }
            else if(nums[mid] < target){
                l=mid+1;
                mid = (l+r)/2;
            }else{
                r=mid;
                mid = (l+r)/2;
            }
        }
        return 0;
    }

    //index当前下标，flag为true表正向搜索
    int cntNum(int index,vector<int> nums,bool flag = true){
        int i = flag?index+1:index-1;
        int symbol = flag?1:-1;
        int cnt=0;
        for(;i>=0 && i<nums.size();i+=symbol){
            if(nums[i] == nums[index])
                cnt++;
        }
        return cnt;
    }
};
int main(){
    vector<int> nums = {5,7,7,8,8,10};
    cout<<Solution().search(nums,8)<<endl;
    return 0;
}